package Offer;
import java.util.*;

/*
    从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

    这题是层序遍历的进阶
    思路：首先根结点是二叉树的第一层，将其从队列中出队并将该结点的左右孩子结点都加入队列中，此时
         队列中的结点就是第二层；依次遍历第二层结点依次出队，并将它们的左右孩子入队，新加入的结点就是第三层
         依次类推下去
* */
public class T32II_levelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }

        Deque<TreeNode> queue = new LinkedList<>();     //队列
        List<List<Integer>> res = new ArrayList<>();    //存储结果
        queue.add(root);

        while (!queue.isEmpty()) {
            ArrayList<Integer> it = new ArrayList<>();
//            for (int i = 0; i < queue.size(); i++) {  //在此过程中队列queue的size会变化，所以用i--
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();   //队头元素出队
                it.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(it);
        }
        return res;
    }
}
